{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Frequency Score of a Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxFrequencyScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组的最大频率分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code> 和一个 <strong>正</strong> 整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>数组的 <strong>频率得分</strong> 是数组中 <strong>不同</strong> 值的 <strong>幂次</strong> 之和，并将和对&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code> <strong>取模</strong>。</p>\n",
    "\n",
    "<p>例如，数组 <code>[5,4,5,7,4,4]</code> 的频率得分为 <code>(4<sup>3</sup>&nbsp;+ 5<sup>2</sup>&nbsp;+ 7<sup>1</sup>) modulo (10<sup>9</sup>&nbsp;+ 7) = 96</code> 。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中长度为 <code>k</code> 的 <strong>子数组</strong> 的 <strong>最大&nbsp;</strong>频率得分。你需要返回取模后的最大值，而不是实际值。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;是一个数组的连续部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1,2,1,2], k = 3\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>子数组 [2,1,2] 的频率分数等于 5。可以证明这是我们可以获得的最大频率分数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1,1,1,1], k = 4\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>所有长度为 4 的子数组的频率得分都等于 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-frequency-score-of-a-subarray](https://leetcode.cn/problems/maximum-frequency-score-of-a-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-frequency-score-of-a-subarray](https://leetcode.cn/problems/maximum-frequency-score-of-a-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,2,1,2]\\n3', '[1,1,1,1,1,1]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n",
    "        MAX = 10 ** 9 + 7\n",
    "        c = collections.Counter(nums[0:k])\n",
    "        total = 0\n",
    "        for i in c:\n",
    "            total += pow(i, c[i], MAX)\n",
    "            total %= MAX\n",
    "        ans = total\n",
    "        for i in range(k, len(nums)):\n",
    "            c[nums[i]] += 1\n",
    "            total += pow(nums[i], c[nums[i]], MAX)\n",
    "            if c[nums[i]] > 1:\n",
    "                total -= pow(nums[i], c[nums[i]] - 1, MAX)\n",
    "            c[nums[i - k]] -= 1\n",
    "            if c[nums[i - k]] > 0:\n",
    "                total += pow(nums[i - k], c[nums[i - k]], MAX)\n",
    "            total -= pow(nums[i - k], c[nums[i - k]] + 1, MAX)\n",
    "            total %= MAX\n",
    "            if c[nums[i - k]] == 0:\n",
    "                del c[nums[i - k]]\n",
    "            ans = max(ans, total)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = score = 0\n",
    "        st_map = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x not in st_map:\n",
    "                score += x\n",
    "                st_map[x] = [x]\n",
    "            else:\n",
    "                last = st_map[x][-1]\n",
    "                cur = last * x % MOD\n",
    "                score += cur - last\n",
    "                st_map[x].append(cur)\n",
    "            if i >= k - 1:\n",
    "                ans = max(ans, score % MOD)\n",
    "                x = nums[i - k + 1]\n",
    "                st = st_map[x]\n",
    "                score -= st.pop()\n",
    "                if st: score += st[-1]\n",
    "                else: del st_map[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n",
    "        m=max(nums)+1\n",
    "        tempn=[0]*m\n",
    "        tempm=[1]*m\n",
    "        ans=res=0\n",
    "        mod=1000000007\n",
    "        n=len(nums)\n",
    "        for i in range(k):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res-=tempm[nums[i]]\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%mod\n",
    "        ans=max(ans,res%mod)\n",
    "        for i in range(k,n):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res=(res-tempm[nums[i]])%mod\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%mod\n",
    "\n",
    "            res=(res-tempm[nums[i-k]])%mod\n",
    "            tempn[nums[i-k]]-=1\n",
    "            tempm[nums[i-k]]//=nums[i-k]\n",
    "            if tempn[nums[i-k]]>0:\n",
    "                res=(res+tempm[nums[i-k]])%mod\n",
    "            ans=max(ans,res%mod)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n",
    "        tempn=[0]*1000001\n",
    "        tempm=[1]*1000001\n",
    "        ans=res=0\n",
    "        mod=1000000007\n",
    "        n=len(nums)\n",
    "        for i in range(k):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res-=tempm[nums[i]]\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%mod\n",
    "        ans=max(ans,res%mod)\n",
    "        for i in range(k,n):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res=(res-tempm[nums[i]])%mod\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%mod\n",
    "\n",
    "            res=(res-tempm[nums[i-k]])%mod\n",
    "            tempn[nums[i-k]]-=1\n",
    "            tempm[nums[i-k]]//=nums[i-k]\n",
    "            if tempn[nums[i-k]]>0:\n",
    "                res=(res+tempm[nums[i-k]])%mod\n",
    "            ans=max(ans,res%mod)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n",
    "        tempn=[0]*1000001\n",
    "        tempm=[1]*1000001\n",
    "        ans=0\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(k):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res-=tempm[nums[i]]\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%1000000007\n",
    "        ans=max(ans,res%1000000007)\n",
    "        for i in range(k,n):\n",
    "            if tempn[nums[i]]>0:\n",
    "                res=(res-tempm[nums[i]])%1000000007\n",
    "            tempn[nums[i]]+=1\n",
    "            tempm[nums[i]]*=nums[i]\n",
    "            res=(res+tempm[nums[i]])%1000000007\n",
    "\n",
    "            res=(res-tempm[nums[i-k]])%1000000007\n",
    "            tempn[nums[i-k]]-=1\n",
    "            tempm[nums[i-k]]//=nums[i-k]\n",
    "            if tempn[nums[i-k]]>0:\n",
    "                res=(res+tempm[nums[i-k]])%1000000007\n",
    "            ans=max(ans,res%1000000007)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
